package com.msi.algorithm;

import java.util.ArrayList;
import java.util.List;

import org.apache.log4j.Logger;

import com.msi.Graph;
import com.msi.Main;
import com.msi.Vertex;

/**
 * Implementacja algorytmu CSP z nawrotami
 * 
 * @author Michał Kołodziejski
 */
public class CSPAlgorithm implements Runnable {

    /**
     * Rozpatrywany graf połączeń
     */
    protected Graph graph;

    /**
     * Drzewo stanów algorytmu przeszukiwania
     */
    protected StatesTree tree;

    /**
     * Aktualnie rozpatrywany stan częściowy
     */
    protected State currentState;

    /**
     * Flaga określająca, czy w poprzednim kroku algorytmu został dodany nowy
     * stół
     */
    protected boolean newTableAtLastStep;

    /**
     * Logger
     */
    protected Logger logger = Logger.getLogger(CSPAlgorithm.class);

    protected boolean algorithmFinished;

    protected int minNumberOfTables;

    /**
     * Tworzy nową instancję implementacji algorytmu CSP z nawrotami
     * 
     * @param graph
     *            rozpatrywany graf
     */
    public CSPAlgorithm(Graph graph) {
        this.graph = graph;
        this.currentState = createInitialState();
        this.tree = new StatesTree(this.currentState);
        this.newTableAtLastStep = false;
        this.algorithmFinished = false;
        this.minNumberOfTables = (int) ((this.graph.getNumberOfVertices() + 3) / 4);
    }

    @Override
    public void run() {
        runAlgorithm();
    }

    /**
     * Uruchamia przetwarzanie algorytmu
     */
    public List<Table> runAlgorithm() {
        algorithmFinished = false;
        boolean finished = false;

        int step = 0;
        while (!finished) {
            newTableAtLastStep = currentState.placeCurrentGuest();

            logger.debug("Step: " + step + ", sitting: "
                    + currentState.getNumberOfSittingGuests() + ", state: "
                    + currentState.toString() + ", min tables: "
                    + minNumberOfTables);

            if (currentState.isStateFinal()) {
                if (currentState.getTablesNumber() == minNumberOfTables) {
                    // lepiej nie będzie - od razu zwracamy wynik
                    finished = true;
                    continue;
                }

                if (!newTableAtLastStep) {
                    finished = true;
                    continue;
                }
            }

            currentState = chooseNextState();
            ++step;
        }

        algorithmFinished = true;

        return currentState.getTables();
    }

    /**
     * Zwraca informację, czy algorytm zakończył swoje działanie
     * 
     * @return informacja czy algorytm zakończył swoje działanie
     */
    public boolean isAlgorithmFinished() {
        // nie modyfikujemy tu wartości, więc dostęp nie musi być
        // synchronizowany
        return this.algorithmFinished;
    }

    /**
     * Zwraca rezultat działania algorytmu
     * 
     * @return lista obsadzonych stołów
     */
    public List<Table> getResult() {
        if (!algorithmFinished) {
            throw new RuntimeException(
                    "Próba pobrania wyniku przed zakończeniem działania algorytmu!");
        }

        return currentState.getTables();
    }

    /**
     * Tworzy stan początkowy dla drzewa
     * 
     * @return stan początkowy
     */
    protected State createInitialState() {
        Graph graphCopy = graph.getDeepCopy();
        List<Vertex> sortedVertices = graphCopy
                .getNotVisitedVerticesSortedByDegree(Main.ascendingSort);
        Vertex firstVertex = sortedVertices.get(0);
        List<Table> tablesList = new ArrayList<Table>();

        State initialState = new State(graphCopy, firstVertex, tablesList, null);
        return initialState;
    }

    /**
     * Uaktualnia drzewo stanów
     */
    protected void updateStatesTree() {
        List<State> partialStates = tree.getPartialStatesCopy();

        for (State state : partialStates) {
            if (!state.isStateFinal() && !state.mayHaveMoreChildrenStates()) {
                tree.removePartialState(state);
            }
        }
    }

    /**
     * Wybiera kolejny stan
     * 
     * @return wybrany stan
     */
    protected State chooseNextState() {
        State bestState = currentState;

        // dopóki aktualny stan jest niegorszy niż najlepsze możliwe rozwiązanie
        // - idziemy
        // dalej tą samą scieżką
        if (currentState.getTablesNumber() > minNumberOfTables) {

            List<State> partialStates = tree.getPartialStatesCopy();

            // wybieramy stan o najmniejszej liczbie stołów, jeżeli jest to
            // finalny
            bestState = partialStates.get(0);

            for (State state : partialStates) {
                if (state.getTablesNumber() <= minNumberOfTables) {
                    bestState = state;
                    break;
                }

                if (state.getTablesNumber() < bestState.getTablesNumber()) {
                    bestState = state;

                } else if (state.getTablesNumber() == bestState
                        .getTablesNumber() && state.isStateFinal()) {
                    bestState = state;

                } else if (state.getTablesNumber() == bestState
                        .getTablesNumber()
                        && state.getNumberOfSittingGuests() > bestState
                                .getNumberOfSittingGuests()) {
                    bestState = state;
                }
            }

            if (bestState.isStateFinal()) {
                // jeżeli końcowy - zwracamy od razu
                return bestState;
            }

        }

        // nie końcowy - tworzymy stan potomny i ew. usuwamy aktualny
        State nextState = bestState.createNewChildState();
        if (nextState.mayHaveMoreChildrenStates()) {
            tree.addPartialState(nextState);
        }
        updateStatesTree();

        return nextState;
    }
}
